typedef unsigned char byte;
typedef unsigned short word;
#include "sk_util.h"
char * empty_puzzle=".................................................................................";


//The cell indexes in each of the 9 rows, 9 columns, and 9 squares out of fss
byte cellsInGroup[27][9] =
{
	{ 0, 1, 2, 3, 4, 5, 6, 7, 8},{ 9,10,11,12,13,14,15,16,17},{18,19,20,21,22,23,24,25,26},
	{27,28,29,30,31,32,33,34,35},{36,37,38,39,40,41,42,43,44},{45,46,47,48,49,50,51,52,53},
	{54,55,56,57,58,59,60,61,62},{63,64,65,66,67,68,69,70,71},{72,73,74,75,76,77,78,79,80},
	{ 0, 9,18,27,36,45,54,63,72},{ 1,10,19,28,37,46,55,64,73},{ 2,11,20,29,38,47,56,65,74},
	{ 3,12,21,30,39,48,57,66,75},{ 4,13,22,31,40,49,58,67,76},{ 5,14,23,32,41,50,59,68,77},
	{ 6,15,24,33,42,51,60,69,78},{ 7,16,25,34,43,52,61,70,79},{ 8,17,26,35,44,53,62,71,80},
	{ 0, 1, 2, 9,10,11,18,19,20},{ 3, 4, 5,12,13,14,21,22,23},{ 6, 7, 8,15,16,17,24,25,26},
	{27,28,29,36,37,38,45,46,47},{30,31,32,39,40,41,48,49,50},{33,34,35,42,43,44,51,52,53},
	{54,55,56,63,64,65,72,73,74},{57,58,59,66,67,68,75,76,77},{60,61,62,69,70,71,78,79,80}
};



byte miniline[54][3] =
{	{ 0, 1, 2},{ 3, 4, 5},{ 6, 7, 8},{ 9,10,11},{12,13,14},{15,16,17},{18,19,20},{21,22,23},{24,25,26},
	{27,28,29},{30,31,32},{33,34,35},{36,37,38},{39,40,41},{42,43,44},{45,46,47},{48,49,50},{51,52,53},
	{54,55,56},{57,58,59},{60,61,62},{63,64,65},{66,67,68},{69,70,71},{72,73,74},{75,76,77},{78,79,80},
	{ 0, 9,18},{27,36,45},{54,63,72},{ 1,10,19},{28,37,46},{55,64,73},{ 2,11,20},{29,38,47},{56,65,74},
	{ 3,12,21},{30,39,48},{57,66,75},{ 4,13,22},{31,40,49},{58,67,76},{ 5,14,23},{32,41,50},{59,68,77},
	{ 6,15,24},{33,42,51},{60,69,78},{ 7,16,25},{34,43,52},{61,70,79},	{ 8,17,26},{35,44,53},{62,71,80}
};



COMB9 tcomb9[9+36+84+126] [2];
int indtcomb9[5]={0,9,9+36,9+36+84,129+126};
word indtcomb9rev[512];


class GEN_TABLES{
public:
	GEN_TABLES(){ 
	//============== 
	COMBINE combi; 
	word  trc[9]={8,7,6,5,4,3,2,1,0},trc_s[9];
	int n=-1;
	for(int i=0;i<512;i++) indtcomb9rev[i]=0;
	for(int i=1,i2=8;i<5;i++,i2--){
		combi.First(9,i,trc,trc_s); // build the r/c lot3 tables
		while(++n ) { 
			COMB9 * tc9=tcomb9[n];
			tc9[0].bm.f=tc9[1].bm.f=0;
			for(int j=0;j<9;j++){
				if(j<i2) tc9[1].bm.Set(trc_s[j]);
				else   tc9[0].bm.Set(trc_s[j]);		// smallest in 0		
			}
			tc9[0].nt=tc9[0].bm.String(tc9[0].t);
			tc9[1].nt=tc9[1].bm.String(tc9[1].t);
			indtcomb9rev[tc9[0].bm.f]=n;
			indtcomb9rev[tc9[1].bm.f]=n+(1<<11);
			if(!combi.Next()) break; 	 
		}
	}
		Genbase(); 	Gen2();	 Gen4();
	}
	void Genbase();
	void Gen2();
	void Gen4();

}gen_tables;


// tables generated in the below constructor
int TblMult3[9];  // 3*i
int TblMult9[9];  // 9*i
int Tbldiv3[27]; //i/3 eg :  mini row or digit in F
byte Tblmod3[27];  // i%3
int TblMod9[81]; //i%9 eg : column in block or cell to column
int Tblofftorow[27];// i/9 relative row within a block  (offset to row)
int Tblofftobox[27];//(i%9)/3offset to box
void GEN_TABLES::Genbase(){
	for(int i=0;i<9;i++){
		TblMult3[i] = 3*i;
		TblMult9[i] = 9*i ;
	}
	for(int i=0;i<27;i++){
		Tbldiv3[i] = i/3;
		Tblmod3[i] = i%3;
		TblMod9[i] = TblMod9[i+27] = TblMod9[i+54] = i%9;
		Tblofftorow[i] = i/9;
		Tblofftobox[i] = (i%9)/3;
	}
}

byte Tbloffset[81]; // giving cell to offset in a band
byte TblBoard_Block[81]; // giving cell -> band 

byte TblCelltoBox[81];// relative position in the box
byte TblCelltoUBox[81];// relative position in the box
byte TblCelltoUCol[81];// relative position in the box

byte TblCelltoRow[81];// relative position in the box
byte TblOtherSameBand[27][8]; // cleaning cells other digits

byte BitCount[512] ; // number of bits in a 9 bits value
byte TblBitToInd[512] ; // value 1 to 9 for 1<<n 
byte TblBitIndex[257] ; // value 0 to 8 for 1<<n 
byte Tblfirst0_8[512]; // lowest bit set to 1  bits 1_9

void GEN_TABLES::Gen2(){
	for(int i=0;i<81;i++){
		Tbloffset[i]=i%27;
		TblBoard_Block[i] =i/27;
		TblCelltoBox[i]=3*((i%27)/9) +i%3 ;
		TblCelltoBox[i]=i/9;
		TblCelltoUBox[i]=TblCelltoBox[i]+18;
		TblCelltoUCol[i]=TblMod9[i]+9;
	}

	byte *p=TblOtherSameBand[0];
	for(int i=0;i<27;i++){
		int digit=i/3,blk=i%3;
		for(int j=0;j<9;j++)if(j-digit) (*p++) = (3*j+blk) ;
	}

	for(int i=0;i<512;i++){
		int n=0,po=0;
		for(int j=8;j>=0;j--) if(i &(1<<j)){
			n++; po=j;
		}
		int bti= (n==1)? po+1:0;
		TblBitToInd[i]= bti;
		Tblfirst0_8[i] = po;
		BitCount[i] = n;
	}
	for(int i=0;i<256;i++) TblBitIndex[i]=0;
	for(int i=1;i<9;i++) TblBitIndex[1<<i]=i;
}


byte tv_string[1024];
word tv_strindex[256];
void GEN_TABLES::Gen4(){
	tv_strindex[0]=0;
	int n=0;
	for(int i=1;i<256;i++){
		for(int j=0;j<9;j++)
			if(i & (1<<j))	tv_string[n++]=j;
		tv_strindex[i]=n;
	}
}

word BF16::String(word * r){  
	if(!f)	return 0;
	word n=0;
	int byte1=f & 0xff;
	if(byte1){
		int il=tv_strindex[byte1];
		for(int  i=tv_strindex[byte1-1];i<il;i++){
			r[n++]=tv_string[i];
		}
	}
	if(f & (1<<8)) r[n++]=8; // digit 9 there
	return n;	
}

char * BF16::StringOut(char * out){
	if(!f)	{out[0]=0; return out;}
	word n=0,drb=0;
	int byte1=f & 0xff;
	if(byte1){
		int il=tv_strindex[byte1];
		for(int  i=tv_strindex[byte1-1];i<il;i++){
			out[n++]=tv_string[i]+'1';
		}
	}
	if(f & (1<<8)) out[n++]='9'; // digit 9 there
	out[n]=0;
	return out;	
}

/* First is the initial call for the task
   n;p is the classical math sense

   n total number of objects
   p number of object to select (maxi is p=10)

   d in the entry table
   f is the result table  both size n
*/
 
 void COMBINE::First(int ne,int pe,word * d, word * f )    {
	 entry=d; 
	 output=f;   
	 p=pe;  
	 if(p>10)
		 p=10;  // safety measure, not auhorised
	 lim=p-1; 
	 n=ne;
     for(UINT i=0,v=n-p;i<p;i++,v++) 
		 inds[i]=v;
     Sort();
 }
 /* move step by step from p upper index to p lower index
    return 1 if ok;  0 if over
 */
 int COMBINE::Next()  {
	 if(inds[lim]==lim) 
		 return 0; // finished
     int i=0; 
	 while(inds[i]==i) 
		 i++; // lock for first that can go down
	 inds[i]--; // back one for that one
	 UINT v=inds[i];  // an restart below with no hole
	 while(i--) inds[i]=--v;
	 Sort();    
	 return 1;}

/* send back the entry table with first p as the selection
   others after the selection
   inds is the list of "p" index selected
*/

 void COMBINE::Sort()   { 
	 UINT is=0,js=n-p,jns=0;
	 for(UINT i=0;i<n;i++) {
		 if(i-inds[is] ){
		   output[jns++]=entry[i]; 
		   continue;
		}
	    output[js++]=entry[i];
		if(is<p-1)   // don't pass the limit of the table inds
			is++;   
	 }   

 }  
